#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dist(n, vector<int>(n, -1));
        queue<pair<int, int>> q;
        int landCount = 0, oceanCount = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    q.push({ i, j });
                    landCount++;
                }
                else {
                    oceanCount++;
                }
            }
        }
        if (landCount == 0 || oceanCount == 0) {
            return -1;
        }
        vector<pair<int, int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        int maxDist = 0;
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto [dx, dy] : dirs) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    maxDist = max(maxDist, dist[nx][ny]);
                    q.push({ nx, ny });
                }
            }
        }
        return maxDist;
    }
};